B-splines

B-splines are a more general type of curve than Bezier curves. In a B-spline each control point is associated with a basis function.

$${\bf P}(t) = \sum_{i=1}^{n+1} N_{i,k}(t) {\bf P}_i, t_{\min} \leq t < t_{\max}$$ (87)

There are n + 1 control points, ${\bf P}_1, {\bf P}_2, \ldots, {\bf P}_{n+1}$. The N_i,k basis functions are of order k(degree k-1). k must be at least 2 (linear), and can be no more than n+1 (the number of control points). The important point here is that the order of the curve (linear, quadratic, cubic,...) is therefore not dependent on the number of control points (which it is for Bezier curves, where k must always equal n+1).

Equation 87 defines a piecewise continuous function. A knot vector, $(t_1, t_2,\ldots, t_{k+(n+1)})$, must be specified. This determines the values of t at which the pieces of curve join, like knots joining bits of string. It is necessary that:

$$t_i \leq t_{i+1}, \forall i$$ (88)

The N_i,k depend only on the value of k and the values in the knot vector. N is defined recursively as:

 

$$\left\{ \begin{array}{ll} 1, & t_i \leq t < t_{i+1} \\ 0, & \mbox{otherwise} \end{array}\right.$$ N_i,1(t) =

$$\frac{t-t_i}{t_{i+k-1} - t_i} N_{i,k-1}(t) + \frac{t_{i+k}-t}{t_{i+k} - t_{i+1}} N_{i+1,k-1}(t)$$ N_i,k(t) = (89)

This is essentially a modified version of the idea of taking linear interpolations of linear interpolations of linear interpolations$\ldots$n

At this point it would be instructive for you to work out N_1,1, N_2,1, N_3,1, N_1,2, N_2,2, N_1,3 for the knot vector (0,2,3,6). It helps if you draw the graphs for these functions.

There are several things that you should note about these equations. Each N_i,k(t) depends only on the k+1 knot values from t_i to t_i+k. N_i,k(t)=0 for t < t_i or $t \geq t_{i+k}$ so ${\bf P}_i$ only influences the curve for $t_i \leq t < t_{i+k}$. Formally, ${\bf P}(t)$ is a polynomial of order k (degree k-1) on each interval $t_i \leq t < t_{i+1}$. Across the knots ${\bf P}(t)$ is C^k-2-continuous. ${\bf P}(t)$ is, of course, continuous in all its derivatives between the knots. ${\bf P}(t)$ is validly defined for $t_{\min} \leq t < t_{\max}$ where $t_{\min}=t_k$and $t_{\max} = t_{n+2}$. Even more properties of B-splines are described in Rogers and Adams pp. 306-7.

The knot vector

The above explanation shows that the knot vector is very important. The knot vector can, by its definition, be any sequence of numbers provided that each one is greater than or equal to the preceding one. Some types of knot vector are more useful than others. Knot vectors are generally placed into one of three categories: uniform, open uniform, and non-uniform.

Uniform.

These are knot vectors for which

$$t_{i+1} - t_i = \mbox{constant}, \forall i$$ (90)

For example:

$$\begin{array}{l} \ [1,2,3,4,5,6,7,8]\\ \ [0,1,2,3,4,5]\\ \ ... ...25,0.5,0.75,1.0]\\ \ [-2.5,-1.4,-0.3,0.8,1.9,3 .0] \end{array}$$

Open Uniform.

These are uniform knot vectors which have kequal knot values at each end:

$$\begin{array}{rl} t_i = t_1, & i \leq k \\ t_{i+1} - t_i = \... ...& k \leq i < n+2\\ t_i = t_{k+(n+1)}, & i \geq n+2 \end{array}$$ (91)

For example:

$$\begin{array}{ll} \ [0,0,0,0,1,2,3,4,4,4,4] & (k=4)\\ \ [1,1... ....1,0.1,0.1,0.1,0.3,0.5,0.7,0.7,0.7,0.7,0.7] & (k=5) \end{array}$$

Non-uniform.

This is the general case, the only constraint being the standard $t_i \leq t_{i+1}, \forall i$(Equations 88). For example:

$$\begin{array}{l} \ [1,3,7,22,23,23,49,50,50] \\ \ [1,1,1,2,2... ...,6,6,7,7,7] \\ \ [0.2,0.7,0.7,0.7,1.2,1.2,2.9,3.6] \end{array}$$

The shapes of the N_i,k basis functions are determined entirely by the relative spacing between the knots. Scaling ( $t_i'=\alpha t_i, \forall i$) or translating ( $t_i'= t_i + \Delta t, \forall i$) the knot vector has no effect on the shapes of the N_i,k.

The above gives a description of the various types of knot vector but it doesn't really give you any insight into how the knot vector determines the shape of the curve. The following subsections look at the different types of knot vector in more detail. However, the best way to get to feel for these is to derive and draw the basis functions yourself.

Uniform knot vector

For simplicity, let t_i = i (this is allowable given that the scaling or translating the knot vector has no effect on the shapes of the N_i,k). The knot vector thus becomes $[1,2,3,\ldots,k+(n+1)]$ and Equation 89 simplifies to:

$$\left\{ \begin{array}{ll} 1, & i \leq t < i+1 \\ 0, & \mbox{otherwise} \end{array}\right.$$ N_i,1(t) =

$$\frac{t-i}{k-1} N_{i,k-1}(t) + \frac{i+k-t}{k-1} N_{i+1,k-1}(t)$$ N_i,k(t) = (92)

You should be easily able to graph the first few of these for yourself. The principle thing to note about the uniform basis functions is that, for a given order k, the basis functions are simply shifted versions of one another.

Things you can change about a uniform B-spline

With a uniform B-spline, you obviously cannot change the basis functions (they are fixed because all the knots are equispaced). However you can alter the shape of the curve by modifying a number of things:

Moving control points.

Moving the control points obviously changes the shape of the curve.

Multiple control points.

Sticking two adjacent control points on top of one another causes the curve to pass closer to that point. Stick enough adjacent control points on top of one another and you can make the curve pass through that point.

Order.

Increasing the order k increases the continuity of the curve at the knots, increases the smoothness of the curve, and tends to move the curve farther from its defining polygon.

Joining the ends.

You can join the ends of the curve to make a closed loop. Say you have M points, ${\bf P}_1,\ldots,{\bf P}_M$. You want a closed B-spline defined by these points. For a given order, k, you will need M+(k-1) control points (repeating the first k-1 points): ${\bf P}_1,\ldots,{\bf P}_M,{\bf P}_1,\ldots,{\bf P}_k-1$. Your knot vector will thus have M+2k-1 uniformly spaced knots.

Open uniform knot vector

The previous section intimated that uniform B-splines can be used to describe closed curves: all you have to do is join the ends as described above. If you do not want a closed curve, and you use a uniform knot vector, you find that you need to specify control points at each end of the curve which the curve doesn't go near.

If you wish your B-spline to start and end at your first and last control points then you need an open uniform knot vector. The only difference between this and the uniform knot vector being that the open uniform version has k equal knots at each end.

An order k open uniform B-spline with n+1=k points is the Bezier curve of order k. It would be a useful exercise for you to prove this for k=3. For ease of calculation take the knot vector to be [0,0,0,1,1,1].

The difference between uniform and open uniform

It may help, at this stage, to compare a particular uniform and an equivalent open uniform knot vector. Unfortunately the translation from LaTeX to HTML couldn't cope with this section of the notes, so it has had to be deleted. It appears in the paper version.

Non-uniform knot vector

Any B-spline whose knot vector is neither uniform nor open uniform is non-uniform. Non-uniform knot vectors allow any spacing of the knots, including multiple knots (adjacent knots with the same value). We need to know how this non-uniform spacing affects the basis functions in order to understand where non-uniform knot vectors could be useful. It transpires that there are only three cases of any interest: (1) multiple knots (adjacent knots equal); (2) adjacent knots more closely spaced than the next knot in the vector; and (3) adjacent knots less closely spaced than the next knot in the vector. Obviously, case (3) is simply case (2) turned the other way round.

Multiple knots.

A multiple knot reduces the degree of continuity at that knot value. Across a normal knot the continuity is C^k-2. Each extra knot with the same value reduces continuity at that value by one. This is the only way to reduce the continuity of the curve at the knot values. If there are k-1 (or more) equal knots then you get a discontinuity in the curve.

Close knots.

As two knots' values get closer together, relative to the spacing of the other knots, the curve moves closer to the related control point.

Distant knots.

As two knots' values get further apart, relative to the spacing of the other knots, the curve moves further away from the related control point.

Use of non-uniform knot vectors

Standard procedure is to use uniform or open uniform B-splines unless there is a very good reason not to do so. Moving two knots closer together tends to move the curve only slightly and so there is usually little point in doing it. This leads to the conclusion that the main use of non-uniform B-splines is to allow for multiple knots, which adjust the continuity of the curve at the knot values.

However, non-uniform B-splines are the general form of the B-spline because they incorporate open uniform and uniform B-splines as special cases. Thus we will talk about non-uniform B-splines when we mean the general case, incorporating both uniform and open uniform.

What can you do to control the shape of a B-spline?

• Move the control points.
• Add or remove control points.
• Use multiple control points.
• Change the order, k.
• Change the type of knot vector.
• Change the relative spacing of the knots.
• Use multiple knot values in the knot vector.

What should the defaults be?

If there are no pressing reasons for doing otherwise, your B-spline should be defined as follows:

• k=4 (cubic);
• no multiple control points;
• uniform (for a closed curve) or open uniform (for an open curve) knot vector.

B-spline patches

We generalise from B-spline curves to B-spline surfaces in the same way as we did for Bezier patches. Take a tensor product of two versions of Equation 87.

$${\bf P}(s,t) = \sum_{i=1}^{m+1} \sum_{j=1}^{n+1} {\bf P}_{i,j... ...l}(t), s_{\min} \leq s < s_{\max}, t_{\min} \leq t < t_{\max}$$ (93)

where it is usual for the patch to have the same order (i.e. k=l) in both directions.